Turnpike is a console application I originally developed for academic purposes.
This software implements an algorithm that solves the turnpike problem, a not quite well-known problem of computer science, in a fast and memory-efficient way. If you're not interested in algorithms, probably you won't find much interest in it.
The turnpike problem can be formulated as follows: locate all access entries in a highway provided only the distances between each pair of them are known. The first access entry lies at location 0; the other ones should be found.
The input data is a multiset of n (n − 1) / 2 positive integers, the result is a set of n non negative integers always containing 0, where n is a positive integer (in the actual implementation n is always greater than 1).
An interesting property of the turnpike problem is solution symmetry: if you know a solution for an instance of the problem, you can obtain a symmetrical solution by flipping the location of all access entries about the middle of the highway. It should be noted that two symmetrical solutions may be identical anyway.
Turnpike runs on Windows 2000, XP, 2003, Vista and later versions of the Windows operating systems. If the source code is rebuilt with a different compiler, other platforms could be supported.
Click on the links below for available downloads.
Turnpike is a console application with no graphical interface.
For usage reference, please type Turnpike /? at the command line prompt.
The problem solving algorithm implements a search pattern known as backtracking search. The algorithm works by tentatively arranging new access entries until all input distances are fit in a solution, or until some distances cannot be fit and a dead-end is reached. When an end is reached, the last steps are undone until a new, different arrangement to branch into is found backwards in the solution tree.
In the first step, the first access entry at location 0 is arranged. No alternatives exist here, so no branching may occur. If the input multiset is empty, one solution is found containing only the access entry at location 0 and the algorithm terminates. Note anyway that an empty multiset can only be generated programmatically as the input console will require you to provide at least one distance!
In the second step, the last access entry is arranged: since the first access entry lies at location 0, the last entry has the location specified by the largest input distance itself. Just as in the previous step, no branching is possible here. Once the first and last access entries are located, the largest input distance is marked as assigned: assigned distances are those for which a start and an end location is already known. If no other elements exist in the input multiset, one solution is found containing only the two access entries arranged, and the algorithm terminates.
In the third step, the second largest input distance is used to locate a new access entry moving forth from the first entry or back from the last one (both the first and last entries have been located before). Although two possibilities exist here, only one of them needs to be considered, as the two arrangements are symmetrical and so are the solutions that can be reached from each of them. Note that in order for this step to be possible, another distance must be found in the input multiset: the distance between the new entry and the other end of the highway. If this distance is also found, then the arrangement is possible and both distances are marked as assigned. If this distance is not found, the arrangement is impossible and the problem has no solution. In case no more unassigned distances exist in the input multiset, the access entries found build one solution to the problem; another solution will be the symmetrical one if it's not identical.
In the following steps, the algorithm proceeds as follows: it picks the largest still unassigned input distance and tries to arrange a new access entry that lies at that distance either from the start or to the end of the highway. This step implies branching in two search paths, each of which will or will not lead to any solutions; the branching order is chosen randomly rather than arbitrarily. As a new access entry is set, the distances between the new access entry and each of the previously found access entries are calculated and marked as assigned. If any of these calculated distances are not found in the input multiset, the current search path is discarded as it will not lead to any solutions. Note that this includes the case where the new access entry overlaps with another access entry, as the distance between them would be 0 which is not an element of the input multiset. In the last step of a search path it is possible for the new access entry locations to be equal: when this happens, branching does not occur and only one case is considered instead.
Turnpike was built using Microsoft Visual C++ 2008 and also tested with Borland C++ 5.2 and MinGW.
The source code package contains the Microsoft Visual C++ 2008 project used to build the executable file and also a C++BuilderX project for the Borland compiler and an Eclipse project for MinGW.
Turnpike 1.0 was released on 25th January 2009 and is copyright © Francesco Trotta 2009.
Turnpike is provided as it is with no warranty of any kind. You are welcome to redistribute this software.
You can contact the author by sending an e-mail to: ft1@ft1.